문제를 분석할 때 확률을 이용, 모든 가능한 입력의 분포에 대한 수행 시간의 평균(평균 수행 시간)을 구한다.

확률과 무작위성을 통해 알고리즘의 일부가 랜덤하게 동작하도록 함, 난수 생성기가 리턴하는 값의 분포에 대한 수행시간의

평균값(기대 수행 시간)